Imports System.Collections.Generic
Imports System.Text

Namespace Core
	<Record(FieldMapping := FieldMapping.ExplicitColumnsOnly)> _
	Friend NotInheritable Class NdxPage
		Inherits Record
		Private mEntries As List(Of NdxEntry)
		Friend mParentPage As NdxPage
		Friend mIsModified As Boolean
		'internal int mNbChildEntries;

		Public Sub New()
			EntriesClear()
		End Sub

		Friend Property ParentPage() As NdxPage
			Get
				Return mParentPage
			End Get
			Set
				If mParentPage Is value Then
					Return
				End If
				mParentPage = value
			End Set
		End Property

		Private Sub EntriesClear()
			If mEntries Is Nothing Then
				mEntries = New List(Of NdxEntry)()
			Else
				mEntries.Clear()
			End If
			#If DUMP_INSERTS Then
			If mHolder Is Nothing Then
				Return
			End If
			System.Diagnostics.Trace.WriteLine("Entries.Clear " & " in page #" & Me.RecordNo)
			Dump("      ")
			#End If
		End Sub

		Private Sub EntriesRemove(pos As Integer)
			mEntries.RemoveAt(pos)
		End Sub


		Private Sub EntriesRemoveRange(pos As Integer, count As Integer)
			mEntries.RemoveRange(pos, count)
			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("Entries.RemoveRange @" & pos & " count:" & count & " in page #" & Me.RecordNo)
			Dump("      ")
			#End If
		End Sub


		Private Sub EntriesInsert(pos As Integer, newEntry As NdxEntry)
			#If DEBUG Then
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			Dim cmpArray As Integer() = New Integer(ndxFile.mSortFieldsCount - 1) {}
			Dim cmp As Integer
			If pos > 0 Then
				Dim previousEntry As NdxEntry = GetEntry(pos - 1)
				cmp = newEntry.ChainCompare(cmpArray, ndxFile, previousEntry)
				If cmp < 0 Then
					Dump("NdxPage.EntriesInsert:", "")
					System.Diagnostics.Debug.Assert(False, "Node should be bigger than previous node.")
				End If
			End If
			If pos < mEntries.Count Then
				Dim nextEntry As NdxEntry = GetEntry(pos)
				cmp = newEntry.ChainCompare(cmpArray, ndxFile, nextEntry)
				If cmp > 0 Then
					Dump("NdxPage.EntriesInsert:", "")
					System.Diagnostics.Debug.Assert(False, "Node should be less than previous node.")
				End If
			End If
			#End If
			mEntries.Insert(pos, newEntry)
			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("Entries.Insert @" & pos & ":" & newEntry.Fields.ToString() & " #" & newEntry.DbfRecordNo & " in page #" & Me.RecordNo)
			Dump("      ")
			#End If
		End Sub

		Friend Sub OnReadRecord(buffer As Byte())
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)

			#If DUMP_READ_RECORD Then
			System.Diagnostics.Trace.WriteLine("NdxPage.OnReadRecord Page#" & Me.RecordNo)
			System.Diagnostics.Trace.WriteLine(Utils.HexDump(buffer))
			#End If
			EntriesClear()
			Dim nbEntries As Integer = buffer(0) + (buffer(1) << 8) + (buffer(2) << 16) + (buffer(3) << 24)
			'+BitConverter.ToInt32(buffer, 0);
			Dim pos As Integer = 4
			' int recordWidth = ndxFile.mSortFieldsWriter.RecordWidth;
			Dim fieldsBuffer As [Byte]() = ndxFile.mSortFieldsReadBuffer
			For i As Integer = 0 To nbEntries - 1
                Dim ndxEntry As NdxEntry = New NdxEntry()

                ndxEntry.mNdxNativeLowerPageNo = CInt(buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) + (buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) << 8) + (buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) << 16) + (buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) << 24))
                ndxEntry.DbfRecordNo = CInt(buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) + (buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) << 8) + (buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) << 16) + (buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos), pos - 1)) << 24))

				' 3.67% next line
				Dim fields As Object = ndxFile.mSortFieldsConstructor.Invoke(Nothing)

				' 35.30% next line
				Array.Copy(buffer, pos, fieldsBuffer, 0, fieldsBuffer.Length)

				' 18.66% next line
				ndxFile.mSortFieldsWriter.mQuickReadMethod(ndxFile, fieldsBuffer, fields)
				pos += ndxFile.mSortFieldsWriter.RecordWidth
				' fieldsBuffer.Length;
				ndxEntry.Fields = DirectCast(fields, SortFields)
				'ndxEntry.RecordBuffer = buffer;
				#If DUMP_READ_RECORD Then
				System.Diagnostics.Trace.WriteLine("  Entry " & i & " (Page #" & Me.RecordNo & ") " & fields.ToString() & " " & ndxEntry.Fields.ToString() & " " & ndxEntry.DbfRecordNo)
				#End If

				EntriesInsert(i, ndxEntry)
			Next
		End Sub

		Friend Sub OnFillWriteBuffer(buffer As Byte())
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			Dim nbEntries As Integer = EntriesCount
			buffer(0) = CByte(nbEntries And &Hff)
			buffer(1) = CByte(nbEntries >> 8 And &Hff)
			buffer(2) = CByte(nbEntries >> 16 And &Hff)
			buffer(3) = CByte(nbEntries >> 24 And &Hff)
			Dim pos As Integer = 4
			' we are called by destructors in different threads
			' so we can't use a shared buffer
			Dim fieldsBuffer As [Byte]() = New Byte(ndxFile.mSortFieldsWriter.RecordWidth - 1) {}
			For i As Integer = 0 To nbEntries - 1
                Dim ndxEntry As NdxEntry = GetEntry(i)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.mNdxNativeLowerPageNo And &Hff)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.mNdxNativeLowerPageNo >> 8 And &Hff)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.mNdxNativeLowerPageNo >> 16 And &Hff)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.mNdxNativeLowerPageNo >> 24 And &Hff)

				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.DbfRecordNo And &Hff)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.DbfRecordNo >> 8 And &Hff)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.DbfRecordNo >> 16 And &Hff)
				buffer(System.Math.Max(System.Threading.Interlocked.Increment(pos),pos - 1)) = CByte(ndxEntry.DbfRecordNo >> 24 And &Hff)

				' The next 2 lines take up about 45% of the total method time. Can we prevent from serializing?
				ndxFile.mSortFieldsWriter.mQuickWriteMethod(ndxFile, fieldsBuffer, ndxEntry.Fields)
				Array.Copy(fieldsBuffer, 0, buffer, pos, fieldsBuffer.Length)
				pos += fieldsBuffer.Length
			Next
		End Sub

		Friend ReadOnly Property EntriesCount() As Integer
			Get
				Return mEntries.Count
			End Get
		End Property

		Friend Function GetEntry(pos As Integer) As NdxEntry
			Return mEntries(pos)
		End Function

		Private Sub SetEntry(pos As Integer, newEntry As NdxEntry)
			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("Setting entry #" & pos & ":" & newEntry.Fields.ToString() & " #" & newEntry.DbfRecordNo & " in page #" & Me.RecordNo)
			#End If
			mEntries(pos) = newEntry
		End Sub

		Friend Sub LocateAndInsert(newEntry As NdxEntry)
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			Dim originalPos As Integer = FindInsertPos(newEntry, ndxFile)
			Dim pos As Integer = originalPos

			If pos = EntriesCount Then
				pos -= 1
			End If

			Dim hasLowerPage As Boolean = (pos >= 0 AndAlso GetEntry(pos).LowerPageRecordNo <> Int32.MaxValue)

			If hasLowerPage Then
				' returnNullIfNotInCache 
                Dim ndxPage2 As NdxPage = TryCast(ndxFile.InternalGetPage(Me, GetEntry(pos).LowerPageRecordNo, False), NdxPage)
				ndxPage2.LocateAndInsert(newEntry)
			Else
				InsertInThisPage(newEntry, originalPos)
			End If
		End Sub

		Private Sub InsertInThisPage(newEntry As NdxEntry, pos As Integer)

			#If DUMP_INSERTS Then
			working += 1
			System.Diagnostics.Trace.WriteLine("Inserting entry " & newEntry.Fields.ToString() & " #" & newEntry.DbfRecordNo & " in page #" & Me.RecordNo)
			#End If
			System.Diagnostics.Debug.Assert(Me.RecordNo <> Int32.MaxValue, "RecordNo should be set.")
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			' find the
			EntriesInsert(pos, newEntry)

			If pos = EntriesCount - 1 Then
				' we inserted in the last entry
				PropagateLastEntryChanged(newEntry)
			End If
			If EntriesCount > ndxFile.mNdxHeader.NoOfKeysPerPage Then
				SplitPage()
			End If
			mIsModified = True
		End Sub

		Private Sub DeleteInThisPage(newEntry As NdxEntry, pos As Integer)

			#If DUMP_INSERTS Then
			working += 1
			System.Diagnostics.Trace.WriteLine("Inserting entry " & newEntry.Fields.ToString() & " #" & newEntry.DbfRecordNo & " in page #" & Me.RecordNo)
			#End If
			System.Diagnostics.Debug.Assert(Me.RecordNo <> Int32.MaxValue, "RecordNo should be set.")
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			' find the
			EntriesRemove(pos)

            If pos = EntriesCount Then
                ' we delete the last entry
                Dim lastEntry As NdxEntry = GetEntry(pos - 1)
                PropagateLastEntryChanged(lastEntry)
            End If
            mIsModified = True
		End Sub

		Private Sub PropagateLastEntryChanged(newEntry As NdxEntry)
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
            Dim page As NdxPage = Me
            Dim parentPage__1 As NdxPage = ParentPage
			Dim pos As Integer
			While parentPage__1 IsNot Nothing
				Dim equal As Boolean
				parentPage__1.FindPos(newEntry, ndxFile, equal, pos)
				If pos = parentPage__1.mEntries.Count Then
					pos -= 1
				End If
                Dim originalParentEntry As NdxEntry = parentPage__1.GetEntry(pos)

				If page.RecordNo <> originalParentEntry.LowerPageRecordNo Then
					ndxFile.Dump()
					System.Diagnostics.Debug.Assert(page.RecordNo = originalParentEntry.LowerPageRecordNo, "invalid LowerPageRecordNo")
				End If
                Dim newParentEntry As New NdxEntry() With { _
                     .DbfRecordNo = newEntry.DbfRecordNo, _
                     .LowerPageRecordNo = page.RecordNo, _
                     .Fields = newEntry.Fields.Clone() _
                }

				#If DUMP_INSERTS Then
				System.Diagnostics.Trace.WriteLine("Propagate LastEntry in page #" & parentPage__1.RecordNo & " entry " & pos)
				System.Diagnostics.Trace.WriteLine("before propagate")
				parentPage__1.Dump("      ")
				#End If

				parentPage__1.SetEntry(pos, newParentEntry)

				#If DUMP_INSERTS Then
				System.Diagnostics.Trace.WriteLine("after propagate")
				parentPage__1.Dump("      ")
				#End If

				If pos < parentPage__1.EntriesCount - 1 Then
					Exit While
				End If
				page = parentPage__1
				parentPage__1 = page.ParentPage
			End While
		End Sub

		Private Function FindInsertPos(newEntry As NdxEntry, ndxFile As NdxFile) As Integer
			Dim pos As Integer
			Dim equal As Boolean
			FindPos(newEntry, ndxFile, equal, pos)
			If equal Then
				Throw New Exception("Duplicated entries in the Index file.")
			End If
			Return pos
		End Function

		Private Sub FindPos(newEntry As NdxEntry, ndxFile As NdxFile, ByRef equal As Boolean, ByRef pos As Integer)
			Dim min As Integer = 0
			Dim max As Integer = EntriesCount - 1
			Dim cmpArray As Integer() = New Integer(ndxFile.mSortFieldsCount - 1) {}
			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("Searching entry '" & newEntry.Fields.ToString() & " #" & newEntry.DbfRecordNo & "' position in page #" & Me.RecordNo)
			Dump("      ")
			#End If

			While max >= min
				Dim mid As Integer = (min + max) \ 2
				Dim other As NdxEntry = GetEntry(mid)
				Dim cmp As Integer = newEntry.ChainCompare(cmpArray, ndxFile, other)
				If cmp > 0 Then
					min = mid + 1
				ElseIf cmp < 0 Then
					max = mid - 1
				Else
					equal = True
					pos = mid
					Return
				End If
			End While
			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("   Result:" & min)
			#End If
			equal = False
			pos = min
		End Sub

		Private Sub SplitPage()

			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("Split page #" & Me.RecordNo)
			#End If
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			' split needed (on save)
			Dim mid As Integer = EntriesCount \ 2
			If ParentPage Is Nothing Then
				ParentPage = DirectCast(ndxFile.NewPage(Nothing), NdxPage)

                Dim rootEntry As NdxEntry = New NdxEntry()
                Dim lastEntry As NdxEntry = GetEntry(EntriesCount - 1)
				rootEntry.DbfRecordNo = lastEntry.DbfRecordNo
				rootEntry.Fields = lastEntry.Fields.Clone()
				rootEntry.LowerPageRecordNo = Me.RecordNo

				ParentPage.EntriesClear()
				ParentPage.EntriesInsert(0, rootEntry)
				ndxFile.mNdxHeader.StartingPageRecordNo = ParentPage.RecordNo

				'ParentPage.mNbChildEntries = mNbChildEntries;
				ParentPage.mIsModified = True
				#If DUMP_INSERTS Then
				System.Diagnostics.Trace.WriteLine("  Create new parent page #" & mParentPage.RecordNo)
					#End If
                mParentPage.Dump("      ")
			End If

            Dim newPage As NdxPage = DirectCast(ndxFile.NewPage(ParentPage), NdxPage)
			newPage.EntriesClear()
			newPage.mIsModified = True
			newPage.ParentPage = ParentPage

			For i As Integer = 0 To mid - 1
				'mNbChildEntries = mNbChildEntries;
				newPage.EntriesInsert(i, GetEntry(i))
                Dim lowerPageRecordNo As Int32 = GetEntry(i).LowerPageRecordNo
				If lowerPageRecordNo <> Int32.MaxValue Then
					' returnNullIfNotInCache 
                    Dim ndxPage2 As NdxPage = TryCast(ndxFile.InternalGetPage(ParentPage, lowerPageRecordNo, True), NdxPage)
					If ndxPage2 IsNot Nothing Then
						ndxPage2.ParentPage = newPage
					End If
				End If
			Next
			EntriesRemoveRange(0, mid)

            Dim midEntry As NdxEntry = newPage.GetEntry(mid - 1)
            Dim newMidEntry As NdxEntry = New NdxEntry() With { _
                 .DbfRecordNo = midEntry.DbfRecordNo, _
                .LowerPageRecordNo = newPage.RecordNo, _
                .Fields = midEntry.Fields.Clone() _
            }

			#If DUMP_INSERTS Then
			System.Diagnostics.Trace.WriteLine("  newPage #" & newPage.RecordNo)
			newPage.Dump("      ")

			System.Diagnostics.Trace.WriteLine("  this page #" & RecordNo)
			Dump("      ")
			#End If
			Dim midEntryPos As Integer = ParentPage.FindInsertPos(newMidEntry, ndxFile)
			ParentPage.InsertInThisPage(newMidEntry, midEntryPos)
		End Sub

		Friend Sub Dump(sender As String, indent As String)
			Dim lastLeaf As NdxEntry = Nothing
            Dump(sender & indent, Me.ParentPage, Nothing, False, lastLeaf)
        End Sub
        Friend Sub Dump([string] As String)
            Dump([string], " ")
        End Sub
		Friend Sub Dump(indent As String, parentPage__1 As NdxPage, parentEntry As NdxEntry, withChildren As Boolean, ByRef lastLeaf As NdxEntry)
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)

            System.Diagnostics.Debug.WriteLine(indent & "Page #" & RecordHolder.RecordNo & " " & Me.EntriesCount & " entries (parent: " & (If(ParentPage Is Nothing, "none", "#" & ParentPage.RecordNo)) & ")")
			System.Diagnostics.Debug.Assert(parentPage__1 Is ParentPage, "Invalid NDX Parent page")
			For i As Integer = 0 To EntriesCount - 1
                Dim e As NdxEntry = GetEntry(i)
                Dim WL As String = indent + "   " + "Entry " + i.ToString + " (page #" + RecordHolder.RecordNo.ToString + ") - "
                WL += " SubPage: "
                System.Diagnostics.Debug.WriteLine(WL) ' (If(e.LowerPageRecordNo = Int32.MaxValue, "none", CDbl("#" + e.LowerPageRecordNo)).ToString) + ", Key: " + e.Fields.ToString() + " #" + e.DbfRecordNo)
				If e.mNdxNativeLowerPageNo <> 0 Then
					'returnNullIfNotInCache
                    Dim subPage As NdxPage = DirectCast(ndxFile.InternalGetPage(Me, CInt(e.LowerPageRecordNo), False), NdxPage)
					If withChildren Then
						subPage.Dump(indent & "    ", Me, e, True, lastLeaf)
					End If
				Else

					#If DEBUG Then
					If lastLeaf IsNot Nothing Then
						Dim cmpArray As Integer() = New Integer(ndxFile.mSortFieldsCount - 1) {}
						Dim cmp As Integer = e.ChainCompare(cmpArray, ndxFile, lastLeaf)
						If cmp <= 0 Then
							System.Diagnostics.Trace.WriteLine("*** ERRROR HERE THE ORDER IS MESSED UP ***")
						End If
					End If
						#End If
					lastLeaf = e
				End If
			Next
		End Sub

		Friend Function CountChildren(maxLevel As Integer) As Integer
			If maxLevel <= 1 Then
				Return EntriesCount
			End If
			' this is just a minimum approximation
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			Dim result As Integer = 0
			For i As Integer = 0 To EntriesCount - 1
                Dim e As NdxEntry = GetEntry(i)
				If e.mNdxNativeLowerPageNo <> 0 Then
					'returnNullIfNotInCache
                    Dim subPage As NdxPage = DirectCast(ndxFile.InternalGetPage(Me, CInt(e.LowerPageRecordNo), False), NdxPage)
					result += subPage.CountChildren(maxLevel - 1)
				Else
					result += 1
				End If
			Next
			Return result
		End Function
        Friend Sub LocateAndDelete(entry As NdxEntry)
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
            Dim equal As Boolean
            Dim originalPos As Integer
            FindPos(entry, ndxFile, equal, originalPos)

            If originalPos = EntriesCount Then
                originalPos -= 1
            End If

            Dim hasLowerPage As Boolean = (originalPos >= 0 AndAlso GetEntry(originalPos).LowerPageRecordNo <> Int32.MaxValue)

            If hasLowerPage Then
                ' returnNullIfNotInCache 
                Dim ndxPage2 As NdxPage = TryCast(ndxFile.InternalGetPage(Me, GetEntry(originalPos).LowerPageRecordNo, False), NdxPage)
                ndxPage2.LocateAndDelete(entry)
            Else
                System.Diagnostics.Debug.Assert(equal = True, "Can't find and remove NDX entry.")
                DeleteInThisPage(entry, originalPos)
            End If
        End Sub

		Friend Function FindFirstEntry(entry As NdxEntry, ByRef pageFrom As NdxPage, ByRef entryNo As Integer) As Boolean
            Dim ndxFile As NdxFile = DirectCast(RecordHolder.mFile, NdxFile)
			Dim equal As Boolean
			Dim originalPos As Integer
			FindPos(entry, ndxFile, equal, originalPos)

			If originalPos = EntriesCount Then
				originalPos -= 1
			End If
			Dim hasLowerPage As Boolean = (originalPos >= 0 AndAlso GetEntry(originalPos).LowerPageRecordNo <> Int32.MaxValue)

			If hasLowerPage Then
				' returnNullIfNotInCache 
                Dim ndxPage2 As NdxPage = TryCast(ndxFile.InternalGetPage(Me, GetEntry(originalPos).LowerPageRecordNo, False), NdxPage)
				ndxPage2.FindFirstEntry(entry, pageFrom, entryNo)
				Return True
			Else
				If equal Then
					pageFrom = Me
					entryNo = originalPos
					Return True
				Else
					pageFrom = Nothing
					entryNo = -1
					Return False
				End If
			End If
		End Function
	End Class
End Namespace
